//给定一个非空的正整数数组 nums ，请判断能否将这些数字分成元素和相等的两部分。 
//
// 
//
// 示例 1： 
//
// 
//输入：nums = [1,5,11,5]
//输出：true
//解释：nums 可以分割成 [1, 5, 5] 和 [11] 。 
//
// 示例 2： 
//
// 
//输入：nums = [1,2,3,5]
//输出：false
//解释：nums 不可以分为和相等的两部分
// 
//
// 
//
// 
// 
//
// 提示： 
//
// 
// 1 <= nums.length <= 200 
// 1 <= nums[i] <= 100 
// 
//
// 
//
// 
// 注意：本题与主站 416 题相同： https://leetcode-cn.com/problems/partition-equal-subset-
//sum/ 
//
// Related Topics 数学 字符串 模拟 👍 66 👎 0

package leetcode.editor.cn;

import java.util.Arrays;

//leetcode submit region begin(Prohibit modification and deletion)
class SolutionOffer2_101 {
    public boolean canPartition1(int[] nums) {
        int sum = Arrays.stream(nums).sum();
        if ((sum & 1) != 0) {
            return false;
        }
        int mid = sum >> 1;
        int[] dp = new int[mid + 1];
        for (int i = 0; i < nums.length; i++) {
            for (int j = mid; j >= nums[i]; j--) {
                dp[j] = Math.max(dp[j], dp[j - nums[i]] + nums[i]);
            }
        }
        if (dp[mid] == mid) return true;
        else return false;
    }

    boolean flag = false;
    boolean[] isBadSum;
    public boolean canPartition(int[] nums) {
        int sum = Arrays.stream(nums).sum();
        if ((sum & 1) != 0) {
            return false;
        }
        int mid = sum >> 1;
        this.isBadSum = new boolean[mid + 1];
        dfs(nums, 0, 0, mid);
        return flag;
    }

    public void dfs(int[] nums, int index, int sum, int mid) {
        if (sum > mid || flag || isBadSum[sum]) {
            return;
        }
        if (sum == mid) {
            flag = true;
            return;
        }
        for (int i = index; i < nums.length; i++) {
            sum += nums[i];  //必须要回溯，因为进入递归前sum已经变了，可以将其放在下一行的参数中，这样就不用回溯
            dfs(nums, i + 1, sum, mid);
            sum -= nums[i];
            isBadSum[sum] = true;
        }
    }


    public static void main(String[] args) {
        boolean b = new SolutionOffer2_101().canPartition(new int[]{1,5,11,5});
        System.out.println(b);
    }
}
//leetcode submit region end(Prohibit modification and deletion)
